Thực đơn
MD5
MD5 chuyển một đoạn thông tin chiều dài thay đổi thành một kết quả chiều dài không đổi 128 bit. Mẩu tin đầu vào được chia thành từng đoạn 512 bit; mẩu tin sau đó được độn sao cho chiều dài của nó chia chẵn cho 512. Công việc độn vào như sau: đầu tiên một bit đơn, 1, được gắn vào cuối mẩu tin. Tiếp theo là một dãy các số zero sao cho chiều dài của mẩu tin lên tới 64 bit ít hơn so với bội số của 512. Những bit còn lại được lấp đầy bằng một số nguyên 64-bit đại diện cho chiều dài của mẩu tin gốc.
Giải thuật MD5 chính hoạt động trên trạng thái 128-bit, được chia thành 4 từ 32-bit, với ký hiệu A, B, C và D. Chúng được khởi tạo với những hằng số cố định. Giải thuật chính sau đó sẽ xử lý các khối tin 512-bit, mỗi khối xác định một trạng thái. Quá trình xử lý khối tin bao gồm bốn giai đoạn giống nhau, gọi là vòng; mỗi vòng gồm có 16 tác vụ giống nhau dựa trên hàm phi tuyến F, cộng mô đun, và dịch trái. Hình 1 mô tả một tác vụ trong một vòng. Có 4 khả năng cho hàm F; mỗi cái được dùng khác nhau cho mỗi vòng:
F ( X , Y , Z ) = ( X ∧ Y ) ∨ ( ¬ X ∧ Z ) {\displaystyle F(X,Y,Z)=(X\wedge {Y})\vee (\neg {X}\wedge {Z})} G ( X , Y , Z ) = ( X ∧ Z ) ∨ ( Y ∧ ¬ Z ) {\displaystyle G(X,Y,Z)=(X\wedge {Z})\vee (Y\wedge \neg {Z})} H ( X , Y , Z ) = X ⊕ Y ⊕ Z {\displaystyle H(X,Y,Z)=X\oplus Y\oplus Z} I ( X , Y , Z ) = Y ⊕ ( X ∨ ¬ Z ) {\displaystyle I(X,Y,Z)=Y\oplus (X\vee \neg {Z})}⊕ , ∧ , ∨ , ¬ {\displaystyle \oplus ,\wedge ,\vee ,\neg } lần lượt chỉ phép XOR, AND, OR và NOT.
Đây là quá trình thực hiện xử lý của 4 hàm F, G, H, I ở trên:
Vòng 1 (Round 1): Ký hiệu [abcd j s i] là bước thực hiện của phép toán a = b + ((a + F(b, c, d) + M[j] + K[i]) <<< s)Quá trình thực hiện 16 bước sau:
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4][ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8][ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12][ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]
Giải thích: ví dụ biểu thức thứ 2 là [DABC 1 12 2], tương đương với:
D = A + ((D + F(A,B,C) + M[1] + K[2]) <<< 12)Nhận xét: Vòng 1 dùng hàm F, Với giá trị j từ 0 -> 15 và i từ 1 -> 16
Vòng 2 (Round 2): Tương tự, ký hiệu [abcd j s i] là của biểu thức: a = b + ((a + G(b, c, d) + M[j] + K[i]) <<< s) Quá trình thực hiện 16 bước:
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]
Nhận xét: Vòng 2 dùng hàm G, với i từ 17 -> 32 và j = 1 + 5j mod 16
Vòng 3 (Round 3):
Tương tự, ký hiệu [abcd j s i] là của biểu thức: a = b + ((a + H(b, c, d) + M[j] + K[i]) <<< s)
Quá trình thực hiện 16 bước:
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 1 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 5 16 47] [BCDA 2 23 48]
Nhận xét: Vòng 3 dùng hàm H, với i từ 33 -> 48 và j =5 + 3j mod 16
Vòng (Round 4):
Tương tự, ký hiệu [abcd j s i] là của biểu thức:
a = b + ((a + I(b,c,d) + M[j] + K[i]) <<< s)
Quá trình thực hiện 16 bước:
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCDb 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]
Nhận xét: Vòng 4 dùng hàm I, với i từ 49 -> 64 và j =7j mod 16
/* Sau đó làm các phép cộng sau. (Nghĩa là cộng vào mỗi thanh ghi giá trị của nó trước khi vào vòng lặp) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
End /* of loop on i */
Bước 5: Tính kết quả message digest.Sau khi thực hiện xong bước 4, thông điệp thu gọn nhận được từ 4 thanh ghi A, B, C, D, bắt đầu từ byte thấp của thanh ghi A và kết thúc với byte cao của thanh ghi D bằng phép nối như sau: Message Digest = A || B || C || D. (|| phép toán nối)
Mã giả cho giải thuật MD5 như sau.
//Chú ý: Tất cả các biến đều là biến không dấu 32 bit và bao phủ mô đun 2^32 khi tính toánvar int[64] r, k//r xác định số dịch chuyển mỗi vòngr[ 0..15]:= {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22} r[16..31]:= {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20}r[32..47]:= {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23}r[48..63]:= {6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21}//Sử dụng phần nguyên nhị phân của sin của số nguyên làm hằng số:for i from 0 to 63 k[i]:= floor(abs(sin(i + 1)) × (2 pow 32))//Khởi tạo biến:var int h0:= 0x67452301var int h1:= 0xEFCDAB89var int h2:= 0x98BADCFEvar int h3:= 0x10325476//Tiền xử lý:append "1" bit to messageappend "0" bits until message length in bits ≡ 448 (mod 512)append bit (bit, not byte) length of unpadded message as 64-bit little-endian integer to message//Xử lý mẩu tin trong đoạn 512-bit tiếp theo:for each 512-bit chunk of message break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15 //Khởi tạo giá trị băm cho đoạn này: var int a:= h0 var int b:= h1 var int c:= h2 var int d:= h3 //Vòng lặp chính: for i from 0 to 63 if 0 ≤ i ≤ 15 then f:= (b and c) or ((not b) and d) g:= i else if 16 ≤ i ≤ 31 f:= (d and b) or ((not d) and c) g:= (5×i + 1) mod 16 else if 32 ≤ i ≤ 47 f:= b xor c xor d g:= (3×i + 5) mod 16 else if 48 ≤ i ≤ 63 f:= c xor (b or (not d)) g:= (7×i) mod 16 temp:= d d:= c c:= b b:= b + leftrotate((a + f + k[i] + w[g]), r[i]) a:= temp //Thêm bảng băm của đoạn vào kết quả: h0:= h0 + a h1:= h1 + b h2:= h2 + c h3:= h3 + dvar int digest:= h0 append h1 append h2 append h3 //(expressed as little-endian)//định nghĩa hàm dịch tráileftrotate (x, c) return (x << c) or (x >> (32-c));
Ghi chú: Thay vì hàm hóa RFC 1321 gốc như trên, phần sau có thể được dùng để tăng độ hiệu quả (hữu ích nếu ngôn ngữ assembly được dùng - còn không, chương trình dịch sẽ tự động tối ưu hóa đoạn mã ở trên):
(0 ≤ i ≤ 15): f:= d xor (b and (c xor d))(16 ≤ i ≤ 31): f:= c xor (d and (b xor c))
Thực đơn
MD5Liên quan
Tài liệu tham khảo
WikiPedia: MD5